// This file is a part of Funky C++.
// Copyright (C) 2011  Valentin David
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
#ifndef __INVERT_BITS_HH
# define __INVERT_BITS_HH

# include "bin_pow.hh"
# include "static_bin_log.hh"
# include <type_traits>

namespace fast {
  template <typename integral_type, int size, int width, integral_type pattern>
  struct repeat_pattern_recurse {
    enum: integral_type {
      value = (integral_type)repeat_pattern_recurse<integral_type,
						    size,
						    2*width,
						    pattern |
						    (pattern << width)>::value
    };
  };

  template <typename integral_type, int size, integral_type pattern>
  struct repeat_pattern_recurse<integral_type, size, size, pattern> {
    enum: integral_type { value = pattern };
  };

  template <typename integral_type, int width, integral_type pattern>
  struct repeat_pattern:
    public repeat_pattern_recurse<integral_type, sizeof(integral_type)<<3,
				  width, pattern>
  {};

  template <typename integral_type, size_t N>
  struct inversion_helper {
    enum: integral_type
      { shift = 1 << (N-1),
	smallpattern = ((integral_type)bin_pow_pow<integral_type, N>::value-1)
	<< shift,
	pattern = repeat_pattern<integral_type, 2*shift, smallpattern>::value
      };
    static void step(integral_type& v) {
      integral_type l = v << shift;
      v >>= shift;
      v = (l & pattern)
	| (v & (pattern >> shift));
      inversion_helper<integral_type, N-1>::step(v);
    }
  };

  template <typename integral_type>
  struct inversion_helper<integral_type, 0u> {
    static void step(integral_type&) {}
  };

  template <typename integral_type, size_t N,
	    size_t Step = static_bin_log<integral_type,
					 sizeof(integral_type)<<3>::value>
  struct static_invert_bits {
    typedef inversion_helper<integral_type, Step> h;
    static const size_t value =
      static_invert_bits<integral_type,
			 ((N << h::shift) & h::pattern)
      | ((N >> h::shift) & (h::pattern >> h::shift)),
      Step-1>::value;
  };

  template <typename integral_type, size_t N>
  struct static_invert_bits<integral_type, N, 0> {
    static const size_t value = N;
  };

  template <typename integral_type>
  inline void invert_bits(integral_type& v) {
    static_assert(std::is_integral<integral_type>::value,
		  "Cannot invert bits on non integral types.");
    static_assert(sizeof(integral_type) ==
		  1<< static_bin_log<integral_type,
				     sizeof(integral_type)>::value,
		  "Type size is not a power of two.");

    inversion_helper<integral_type,
		     static_bin_log<integral_type,
				    sizeof(integral_type)<<3>::value>::step(v);
  }
}

#endif
